package com.yanceysong.codetop.s81_s90;

import com.yanceysong.common.TreeNode;

import java.util.ArrayList;
import java.util.List;

public class S84_Mid_113_路径总和_II {

    /**
     * .S84_Mid_113_路径总和 II
     * .<p>
     * .<a href="https://leetcode.cn/problems/path-sum-ii/">...</a>
     * .<p>
     * .给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
     * .<p>
     * .叶子节点 是指没有子节点的节点。
     * .<p>
     * .示例 1：
     * .<p>
     * .输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
     * .输出：[[5,4,11,2],[5,8,4,5]]
     * .解释：等于目标和的根节点到叶节点路径如下：
     * .5 + 4 + 11 + 2 = 22
     * .5 + 8 + 4 + 5 = 22
     * .<p>
     * .示例 2：
     * .<p>
     * .输入：root = [1,2,3], targetSum = 5
     * .输出：[]
     * .<p>
     * .示例 3：
     * .<p>
     * .输入：root = [1,2], targetSum = 0
     * .输出：[]
     * .<p>
     * .提示：
     * .<p>
     * .树中节点总数在范围 [0, 5000] 内
     * .-1000 <= Node.val <= 1000
     * .-1000 <= targetSum <= 1000
     * .<p>
     * .核心标签：二叉树、深度优先搜索(DFS)、回溯算法
     * .<p>
     * .解题思路：
     * .使用深度优先搜索(DFS) + 回溯算法来遍历所有从根节点到叶子节点的路径
     * .<p>
     * .算法步骤：
     * .1. 从根节点开始，将当前节点值加入路径列表
     * .2. 从目标和中减去当前节点值
     * .3. 判断是否到达叶子节点且剩余目标和为0：
     * .- 如果是，将当前路径加入结果集（注意要创建新的列表副本）
     * .4. 递归遍历左子树和右子树
     * .5. 回溯：移除路径列表中的最后一个元素，恢复状态
     * .<p>
     * .关键洞察：
     * .1. 必须是根节点到叶子节点的完整路径，中间节点不算
     * .2. 回溯时要移除当前节点，保证路径的正确性
     * .3. 添加到结果集时要创建新的ArrayList，避免引用问题
     * .4. 使用减法而不是加法，避免累加变量的传递
     * .<p>
     * .ASCII 图解示例 1：
     * .<p>
     * .输入树结构：targetSum = 22
     * .          5
     * .        /   \
     * .       4     8
     * .      /     / \
     * .     11    13  4
     * .    /  \      / \
     * .   7    2    5   1
     * .<p>
     * .DFS遍历过程（标记✓表示找到目标路径）：
     * .<p>
     * .路径1: 5 → 4 → 11 → 7
     * .当前路径: [5, 4, 11, 7]
     * .路径和: 5 + 4 + 11 + 7 = 27 ≠ 22 ✗
     * .<p>
     * .路径2: 5 → 4 → 11 → 2
     * .当前路径: [5, 4, 11, 2]
     * .路径和: 5 + 4 + 11 + 2 = 22 ✓ (找到第一条路径)
     * .<p>
     * .路径3: 5 → 8 → 13
     * .当前路径: [5, 8, 13]
     * .路径和: 5 + 8 + 13 = 26 ≠ 22 ✗
     * .<p>
     * .路径4: 5 → 8 → 4 → 5
     * .当前路径: [5, 8, 4, 5]
     * .路径和: 5 + 8 + 4 + 5 = 22 ✓ (找到第二条路径)
     * .<p>
     * .路径5: 5 → 8 → 4 → 1
     * .当前路径: [5, 8, 4, 1]
     * .路径和: 5 + 8 + 4 + 1 = 18 ≠ 22 ✗
     * .<p>
     * .最终结果: [[5,4,11,2], [5,8,4,5]]
     * .<p>
     * .回溯过程示意：
     * .<p>
     * .访问节点5: path=[5], remainingSum=17
     * .  ├─ 访问节点4: path=[5,4], remainingSum=13
     * .  │    └─ 访问节点11: path=[5,4,11], remainingSum=2
     * .  │         ├─ 访问节点7: path=[5,4,11,7], remainingSum=-5 (叶子节点，不满足)
     * .  │         │    └─ 回溯: path=[5,4,11]
     * .  │         └─ 访问节点2: path=[5,4,11,2], remainingSum=0 (叶子节点，满足！) ✓
     * .  │              └─ 回溯: path=[5,4,11]
     * .  │         └─ 回溯: path=[5,4]
     * .  │    └─ 回溯: path=[5]
     * .  └─ 访问节点8: path=[5,8], remainingSum=9
     * .       ├─ 访问节点13: path=[5,8,13], remainingSum=-4 (叶子节点，不满足)
     * .       │    └─ 回溯: path=[5,8]
     * .       └─ 访问节点4: path=[5,8,4], remainingSum=5
     * .            ├─ 访问节点5: path=[5,8,4,5], remainingSum=0 (叶子节点，满足！) ✓
     * .            │    └─ 回溯: path=[5,8,4]
     * .            └─ 访问节点1: path=[5,8,4,1], remainingSum=-1 (叶子节点，不满足)
     * .                 └─ 回溯: path=[5,8,4]
     * .            └─ 回溯: path=[5,8]
     * .       └─ 回溯: path=[5]
     * .<p>
     * .时间复杂度：O(n²)
     * .- 需要遍历所有节点：O(n)
     * .- 在最坏情况下（所有路径都满足条件），需要复制路径到结果集：O(n)
     * .- 总体：O(n²)
     * .<p>
     * .空间复杂度：O(n)
     * .- 递归调用栈的深度：O(h)，其中h是树的高度，最坏情况下h=n
     * .- 路径列表：O(h)
     * .- 结果集不计入空间复杂度
     * .- 总体：O(n)
     */

    // 存储所有满足条件的路径
    private final List<List<Integer>> resultPaths = new ArrayList<>();
    // 当前正在构建的路径
    private final List<Integer> currentPath = new ArrayList<>();

    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        // 从根节点开始深度优先搜索
        dfs(root, targetSum);
        return resultPaths;
    }

    /**
     * .深度优先搜索 + 回溯
     * .@param node            当前访问的节点
     * .@param remainingSum    剩余需要凑齐的目标和
     */
    private void dfs(TreeNode node, int remainingSum) {
        // 递归终止条件：节点为空
        if (node == null) {
            return;
        }

        // 1. 将当前节点值加入路径
        currentPath.add(node.val);
        // 2. 更新剩余目标和
        remainingSum -= node.val;

        // 3. 判断是否到达叶子节点且路径和等于目标和
        if (node.left == null && node.right == null && remainingSum == 0) {
            // 找到一条满足条件的路径，将其加入结果集
            // 注意：必须创建新的ArrayList，否则后续的回溯会影响已添加的路径
            resultPaths.add(new ArrayList<>(currentPath));
        }

        // 4. 递归遍历左子树
        dfs(node.left, remainingSum);
        // 5. 递归遍历右子树
        dfs(node.right, remainingSum);

        // 6. 回溯：移除当前节点，恢复路径状态
        // 这样在返回上一层时，路径不包含当前节点
        currentPath.remove(currentPath.size() - 1);
    }

    public static void main(String[] args) {
        S84_Mid_113_路径总和_II solution = new S84_Mid_113_路径总和_II();

        System.out.println("=== 路径总和 II 测试开始 ===");

        // 测试1: 示例1 - 有多条路径满足条件
        System.out.println("\n--- 测试1: 示例1 [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum=22 ---");
        testCase1(solution);

        // 测试2: 示例2 - 无满足条件的路径
        System.out.println("\n--- 测试2: 示例2 [1,2,3], targetSum=5 ---");
        testCase2(solution);

        // 测试3: 示例3 - 路径和不为0
        System.out.println("\n--- 测试3: 示例3 [1,2], targetSum=0 ---");
        testCase3(solution);

        // 测试4: 空树
        System.out.println("\n--- 测试4: 空树 ---");
        testEmptyTree(solution);

        // 测试5: 单节点树 - 满足条件
        System.out.println("\n--- 测试5: 单节点树满足条件 ---");
        testSingleNodeMatch(solution);

        // 测试6: 单节点树 - 不满足条件
        System.out.println("\n--- 测试6: 单节点树不满足条件 ---");
        testSingleNodeNoMatch(solution);

        // 测试7: 只有左子树的路径
        System.out.println("\n--- 测试7: 只有左子树 ---");
        testLeftSkewedTree(solution);

        // 测试8: 只有右子树的路径
        System.out.println("\n--- 测试8: 只有右子树 ---");
        testRightSkewedTree(solution);

        // 测试9: 负数节点值
        System.out.println("\n--- 测试9: 包含负数节点 ---");
        testNegativeValues(solution);

        // 测试10: 所有路径都满足条件
        System.out.println("\n--- 测试10: 所有路径都满足 ---");
        testAllPathsMatch(solution);

        System.out.println("\n=== 所有测试完成 ===");
    }

    /**
     * .测试1: 示例1
     * .树结构：
     * .         5
     * .       /   \
     * .      4     8
     * .     /     / \
     * .    11    13  4
     * .   /  \      / \
     * .  7    2    5   1
     * .targetSum = 22
     * .期望输出：[[5,4,11,2], [5,8,4,5]]
     */
    private static void testCase1(S84_Mid_113_路径总和_II solution) {
        TreeNode root = new TreeNode(5);
        root.left = new TreeNode(4);
        root.right = new TreeNode(8);
        root.left.left = new TreeNode(11);
        root.left.left.left = new TreeNode(7);
        root.left.left.right = new TreeNode(2);
        root.right.left = new TreeNode(13);
        root.right.right = new TreeNode(4);
        root.right.right.left = new TreeNode(5);
        root.right.right.right = new TreeNode(1);

        int targetSum = 22;
        System.out.println("输入: root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = " + targetSum);

        // 创建新实例以避免状态污染
        S84_Mid_113_路径总和_II freshSolution = new S84_Mid_113_路径总和_II();
        List<List<Integer>> result = freshSolution.pathSum(root, targetSum);

        System.out.println("输出: " + result);
        System.out.println("期望: [[5, 4, 11, 2], [5, 8, 4, 5]]");
        assert result.size() == 2 : "应该找到2条路径";
        assert result.get(0).equals(List.of(5, 4, 11, 2)) : "第一条路径应为[5,4,11,2]";
        assert result.get(1).equals(List.of(5, 8, 4, 5)) : "第二条路径应为[5,8,4,5]";
        System.out.println("✓ 测试1通过");
    }

    /**
     * .测试2: 示例2 - 无满足条件的路径
     * .树结构：
     * .      1
     * .     / \
     * .    2   3
     * .targetSum = 5
     * .期望输出：[]
     */
    private static void testCase2(S84_Mid_113_路径总和_II solution) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);

        int targetSum = 5;
        System.out.println("输入: root = [1,2,3], targetSum = " + targetSum);

        S84_Mid_113_路径总和_II freshSolution = new S84_Mid_113_路径总和_II();
        List<List<Integer>> result = freshSolution.pathSum(root, targetSum);

        System.out.println("输出: " + result);
        System.out.println("期望: []");
        assert result.isEmpty() : "应该没有满足条件的路径";
        System.out.println("✓ 测试2通过");
    }

    /**
     * .测试3: 示例3
     * .树结构：
     * .      1
     * .     /
     * .    2
     * .targetSum = 0
     * .期望输出：[]
     */
    private static void testCase3(S84_Mid_113_路径总和_II solution) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);

        int targetSum = 0;
        System.out.println("输入: root = [1,2], targetSum = " + targetSum);

        S84_Mid_113_路径总和_II freshSolution = new S84_Mid_113_路径总和_II();
        List<List<Integer>> result = freshSolution.pathSum(root, targetSum);

        System.out.println("输出: " + result);
        System.out.println("期望: []");
        assert result.isEmpty() : "应该没有满足条件的路径";
        System.out.println("✓ 测试3通过");
    }

    /**
     * .测试4: 空树
     */
    private static void testEmptyTree(S84_Mid_113_路径总和_II solution) {
        System.out.println("输入: root = null, targetSum = 0");

        S84_Mid_113_路径总和_II freshSolution = new S84_Mid_113_路径总和_II();
        List<List<Integer>> result = freshSolution.pathSum(null, 0);

        System.out.println("输出: " + result);
        System.out.println("期望: []");
        assert result.isEmpty() : "空树应该返回空列表";
        System.out.println("✓ 测试4通过");
    }

    /**
     * .测试5: 单节点树 - 满足条件
     * .树结构：5
     * .targetSum = 5
     * .期望输出：[[5]]
     */
    private static void testSingleNodeMatch(S84_Mid_113_路径总和_II solution) {
        TreeNode root = new TreeNode(5);
        int targetSum = 5;
        System.out.println("输入: root = [5], targetSum = " + targetSum);

        S84_Mid_113_路径总和_II freshSolution = new S84_Mid_113_路径总和_II();
        List<List<Integer>> result = freshSolution.pathSum(root, targetSum);

        System.out.println("输出: " + result);
        System.out.println("期望: [[5]]");
        assert result.size() == 1 : "应该找到1条路径";
        assert result.get(0).equals(List.of(5)) : "路径应为[5]";
        System.out.println("✓ 测试5通过");
    }

    /**
     * .测试6: 单节点树 - 不满足条件
     * .树结构：5
     * .targetSum = 10
     * .期望输出：[]
     */
    private static void testSingleNodeNoMatch(S84_Mid_113_路径总和_II solution) {
        TreeNode root = new TreeNode(5);
        int targetSum = 10;
        System.out.println("输入: root = [5], targetSum = " + targetSum);

        S84_Mid_113_路径总和_II freshSolution = new S84_Mid_113_路径总和_II();
        List<List<Integer>> result = freshSolution.pathSum(root, targetSum);

        System.out.println("输出: " + result);
        System.out.println("期望: []");
        assert result.isEmpty() : "应该没有满足条件的路径";
        System.out.println("✓ 测试6通过");
    }

    /**
     * .测试7: 只有左子树
     * .树结构：
     * .      1
     * .     /
     * .    2
     * .   /
     * .  3
     * .targetSum = 6
     * .期望输出：[[1,2,3]]
     */
    private static void testLeftSkewedTree(S84_Mid_113_路径总和_II solution) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.left.left = new TreeNode(3);

        int targetSum = 6;
        System.out.println("输入: root = [1,2,3] (左斜树), targetSum = " + targetSum);

        S84_Mid_113_路径总和_II freshSolution = new S84_Mid_113_路径总和_II();
        List<List<Integer>> result = freshSolution.pathSum(root, targetSum);

        System.out.println("输出: " + result);
        System.out.println("期望: [[1, 2, 3]]");
        assert result.size() == 1 : "应该找到1条路径";
        assert result.get(0).equals(List.of(1, 2, 3)) : "路径应为[1,2,3]";
        System.out.println("✓ 测试7通过");
    }

    /**
     * .测试8: 只有右子树
     * .树结构：
     * .  1
     * .   \
     * .    2
     * .     \
     * .      3
     * .targetSum = 6
     * .期望输出：[[1,2,3]]
     */
    private static void testRightSkewedTree(S84_Mid_113_路径总和_II solution) {
        TreeNode root = new TreeNode(1);
        root.right = new TreeNode(2);
        root.right.right = new TreeNode(3);

        int targetSum = 6;
        System.out.println("输入: root = [1,2,3] (右斜树), targetSum = " + targetSum);

        S84_Mid_113_路径总和_II freshSolution = new S84_Mid_113_路径总和_II();
        List<List<Integer>> result = freshSolution.pathSum(root, targetSum);

        System.out.println("输出: " + result);
        System.out.println("期望: [[1, 2, 3]]");
        assert result.size() == 1 : "应该找到1条路径";
        assert result.get(0).equals(List.of(1, 2, 3)) : "路径应为[1,2,3]";
        System.out.println("✓ 测试8通过");
    }

    /**
     * .测试9: 包含负数节点
     * .树结构：
     * .       5
     * .      / \
     * .    -2   3
     * .    /
     * .   1
     * .targetSum = 4
     * .期望输出：[[5,-2,1]]
     */
    private static void testNegativeValues(S84_Mid_113_路径总和_II solution) {
        TreeNode root = new TreeNode(5);
        root.left = new TreeNode(-2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(1);

        int targetSum = 4;
        System.out.println("输入: root = [5,-2,3,1] (包含负数), targetSum = " + targetSum);

        S84_Mid_113_路径总和_II freshSolution = new S84_Mid_113_路径总和_II();
        List<List<Integer>> result = freshSolution.pathSum(root, targetSum);

        System.out.println("输出: " + result);
        System.out.println("期望: [[5, -2, 1]]");
        assert result.size() == 1 : "应该找到1条路径";
        assert result.get(0).equals(List.of(5, -2, 1)) : "路径应为[5,-2,1]";
        System.out.println("✓ 测试9通过");
    }

    /**
     * .测试10: 所有路径都满足条件
     * .树结构：
     * .      1
     * .     / \
     * .    1   1
     * .targetSum = 2
     * .期望输出：[[1,1], [1,1]]
     */
    private static void testAllPathsMatch(S84_Mid_113_路径总和_II solution) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(1);
        root.right = new TreeNode(1);

        int targetSum = 2;
        System.out.println("输入: root = [1,1,1], targetSum = " + targetSum);

        S84_Mid_113_路径总和_II freshSolution = new S84_Mid_113_路径总和_II();
        List<List<Integer>> result = freshSolution.pathSum(root, targetSum);

        System.out.println("输出: " + result);
        System.out.println("期望: [[1, 1], [1, 1]]");
        assert result.size() == 2 : "应该找到2条路径";
        assert result.get(0).equals(List.of(1, 1)) : "第一条路径应为[1,1]";
        assert result.get(1).equals(List.of(1, 1)) : "第二条路径应为[1,1]";
        System.out.println("✓ 测试10通过");
    }
}

